There are applications in which Boolean functions are manipulated in many fields. As an example, the synthesis and optimization of complex electronic circuits and the analysis of system failures can be based on such manipulation. In the analysis of system failures, a Boolean function can be used to represent the occurrence of a failure as a function of the outside events that could cause that failure. Such a function can be represented in the form of a truth table, Boolean equations and a Karnaugh map. These various known modes of representation make it possible to display each combination of variables (or events) that may exist. However, these representations have the disadvantage that their size grows exponentially as a function of the number of variables appearing in the determination of the function. Thus, for a dependent function with n variables, there are 2.sup.n possible combinations of those variables.
Consequently, if, for example, the function is represented in the form of a truth table, each possible combination of variables and each corresponding value of the function can be represented on the same line, so that for a function with n variables, such a table has n+1 columns and 2.sup.n lines. It can be stored in the memory of a processor, but it takes up a lot of space. And to find the value of the function for a given combination of variables, it may be necessary to go through a certain number of lines in the table, which can have a negative effect on the processing time. Assume, for example, that the combination that you are looking for is the last one on the table; you would have to go through every line in the table to find the corresponding value of the function.
In order to correct the disadvantages of these representations, the idea has been advanced to represent Boolean functions in the form of binary decision graphs or diagrams, called B. D. D., the initials of their name "Binary Decision Diagram" in English.
Before explaining what a binary decision diagram is, some ideas and definitions of the functions and the terminology used should be given.
Assume a function f defined by the following formula: f=x.sub.1 x.sub.2 *+x.sub.1 *x.sub.2 x.sub.3. We say that the formula is a propositional formula, and x.sub.1, x.sub.2, x.sub.3 are propositional variables, corresponding to atomic events capable of causing the appearance of a reference event.
Thus, in the analysis of systems failures, the atomic events are the causes of the failure, and the reference event is a special failure linked to causes combined with one another in certain ways.
The terms "x.sub.1 ", "x.sub.2 ", "x.sub.3 " and "x.sub.1 *", "x.sub.2 *", "x.sub.3 *", which appear in the formula, are literals corresponding to the propositional variables x.sub.1, x.sub.2, x.sub.3. A literal represents how the propositional variable acts in the function, i.e., if the occurrence or non-occurrence of the associated event is decisive or indifferent. x.sub.1 x.sub.2 * and x.sub.1 *x.sub.2 x.sub.3 are literal products. A product is therefore a conjunction of variables and negations of variables.
The first product x.sub.1 x.sub.2 * means that the presence or absence of the third variable x.sub.3 is indifferent.
The formula means that the reference event occurs (f=1) when the first atomic event x.sub.1 occurs (x1=1) and the second x.sub.2 does not occur (x.sub.2 =0) simultaneously, or else when the first event x.sub.1 does not occur simultaneously and the second and third x.sub.2 and x.sub.3 do.
A binary decision graph is composed of a certain number of labels connected to one another by branches. Each label represents a set variable of the function, which has two branches coming off of it. The unit consisting of the label, hence the variable, plus the two branches that come off it forms a node, sometimes called a vertex. Each branch can be either a terminal branch, which ends with a terminal leaf whose value is "0" or "1," or an intermediate branch which ends with the label of another node. One of the branches that comes off a label is called the low or negative branch and represents what happens when the value of the associated variable is "0" (using the conventions mentioned above), while the other branch, called the high or positive branch, shows what happens when the value of the variable is "1." In fact, the tree starts with a single-root variable (a label), called the root, off of which there are two branches, to which other nodes or leaves are connected in cascade.
By going from the root of the tree to the terminal leaf whose value is 1, a combination of literals is set up, for which the function is equal to 1, i.e., a combination (a product) of variables causing the appearance of the reference event shown is produced. Consequently, by taking each of these paths from the root to each of the terminal leaves whose value is 1, you can find each of the combinations of variables causing the appearance of the reference event.
Such a diagram or graph thus makes it possible to display all the combinations of variables of a function in an extremely complete, concise manner. The memory space occupied is less compared to the tables, and the processing time for the functions shown in binary decision graph form is much faster.
What is more, a binary decision graph lends itself specifically to automatic processing with a processor, since each node can be represented using information contained in one memory word of the processor.
Different approaches to the binary decision diagrams have been conceived. Thus, Randal E. Bryant, in a publication that appeared in "IEEE Transactions on Computers," Volume C-35, Number 8, August 1986, showed how the variables, and hence the nodes could be ordered to obtain extremely compact, but perfectly representative graphs of the different combinations of variables appearing in a function.
However, such graphs do not make it possible to carry out effectively or quickly all the manipulations possible on the functions represented in this way. Indeed, some types of analyses require calculation of the prime implicants of the function: for example, this is true when probability studies, occurrence of the root event or any other type of event analysis is performed.
It should be noted that an implicant of a function is a product that implies that function. Also, that an initial product P "contains" a second product P', if the relation P "implies" P' (this is written P=&gt;P') is true. Additionally, a prime implicant is an implicant such that there is no other implicant that contains it.
Going through a binary decision diagram from its root to its terminal leaves does not make it possible to determine directly what the prime implicants of that function are.
Recent approaches have been devised to calculate implicitly the prime implicants of a function from the binary decision diagram which represents it.
Thus, in a publication in November 1991, made by the applicant, whose authors are the inventors mentioned in this application, several methods were presented which make it possible to determine, in an implicit way, the prime implicants of a function.
These methods consist of converting the binary decision diagram, using rules set up by the authors, and representing each literal associated with a propositional variable, such as x.sub.n appearing in a product, by a set of two other variables, a first variable called the occurrence variable O.sub.n and a second variable called a sign variable S.sub.n.
The representation is simple: if the associated occurrence variable is zero, this means that the propositional variable is indifferent in obtaining the product; in this case, the value of the associated sign variable is indifferent; if the occurrence variable is positive or has the binary value "1," this means that the presence or absence of the associated propositional variable is significant for the result, and the associated sign variable indicates whether the corresponding propositional variable is present (by convention, the sign variable =1 in this case) or absent (by convention, the sign variable =0).
The rules developed in this publication take into account the fact that the same product of variables can have several representations and introduced the idea of "meta-product."
Indeed, for n=4, for example, the product {x.sub.2 .multidot.x.sub.3 *.multidot.x.sub.4 } can be represented by the following unit of two sets of occurrence and sign variables [(0111),(1101)] and [(0111),(0101)] which give a canonical representation of the product.
Consequently, a set of different products can be represented by a prime set of reference pairs. By making a logic union of all the pairs in this set, one obtains a second set of pairs constituting the "meta-product," which is therefore the canonical representation of the set of products.
Thus, by making a diagram with set rules that looks like a binary decision diagram and uses occurrence and sign variables, the result is an implicit representation of the set of prime implicants: each path that starts from a root label and ends with a terminal leaf that has a logic value of "1" goes by positive branches associated with occurrence variables and their negative branches, and goes by positive branches associated with sign variables and their negative branches. Going down the negative branch of a given occurrence variable (O.sub.i) on a path means that the corresponding propositional variable does not participate in the product constituting the prime implicant considered.
However, the rules given in this publication are not necessarily best suited for automatic use.
Indeed, calculating the prime implicants of a function represented in the form of a binary decision diagram with a root variable that has a low branch and a high branch coming off of it, which are themselves composed of low sub-branches and high sub-branches, requires calculating the prime implicants of the low branch, calculating the prime implicants of the high branch and calculating the prime implicants of the function representing the intersection of the low branch and the high branch. Then, the final calculation requires an assembly operation combining the prime implicants calculated in this way. This therefore assumes some recursive calculations in parallel, since to end up with the prime implicants of a main branch, it is necessary to have calculated and then combined the set of prime implicants of each of its sub-branches.
The assembly operations (union, intersection, complementation, etc. . . . ) necessary for these successive determinations are no problem to carry out if the different branches and sub-branches are mutually symmetrical in structure. If the ordering is not done correctly, these necessary combinations cannot be made.
Now, the need for symmetrically ordering the variables makes this method extremely memory-intensive and difficult to perform automatically. Sometimes, intermediate implicit representations are obtained which are substantial in size, to keep the symmetry, so that the memory of the machine can be saturated before the set of calculations is finished; and even if the memory is sufficient, the size of the final representation is very large, with either redundant information, or information unnecessary for determining the prime implicants.
To the extent that the memory of the machine was sufficient to establish the implicit representation of the prime implicants, it is still conceivable to simplify it in order to eliminate redundancies. This is difficult, even impossible to do in certain cases.